package  de.cube3d.blitwit.space
{
	import flash.geom.Rectangle;
	import de.cube3d.blitwit.render.BlitSpriteScene;
	
	/**
	 * The BT Space is a binary tree that divides the space into two parts, each
	 * child being of the same class. It is not the fastest way to organize two
	 * dimensional data, but it provides a fairly balanced query efficiency 
	 * for very small and very large objects. 
	 */
	public class BTSpace extends Space
	{
		protected const MIN_CONTENT_LENGTH:int = 8;
		protected var content:Vector.<SpaceObject> = new Vector.<SpaceObject>();
		protected var isSplit:Boolean = false;
		protected var a:BTSpace;
		protected var b:BTSpace;
		protected var aRect:Rectangle = new Rectangle();
		protected var bRect:Rectangle = new Rectangle();
		
		public function get contentCount():int {
			return content.length;
		}
		
		public function get calcChildrenCount():int {
			return 1 + (a?a.calcChildrenCount:0) + (b?b.calcChildrenCount:0);
		}
		
		public function BTSpace(x:Number, y:Number, width:Number, height:Number) 
		{
			super(x, y, width, height);
			if (width > height) {
				aRect.x = x;
				bRect.y = aRect.y = y;
				aRect.width = width * .51; // allow a little bit of overlapping so that we have less stuff that doesn't fit in any of both
				bRect.width = width * .5;
				bRect.height = aRect.height = height;
				
				bRect.x = width *.5 + x;
			} else {
				aRect.y = y;
				bRect.x = aRect.x = x;
				bRect.width = aRect.width = width;
				bRect.height = height * .5;
				aRect.height = height *.51;
				
				bRect.y = height *.5 + y;
			}
		}
		
		override public function set owner (owner:BlitSpriteScene):void{
			_owner = owner;
			if (a) a.owner = owner;
			if (b) b.owner = owner;
		}
		
		override public function get isEmpty ():Boolean {
			return a == null && b == null && content.length == 0;
		}
		
		override protected function _internalAdd (bs:SpaceObject):Boolean {
			return _add(bs, bs.x, bs.y, bs.width, bs.height);
		}
		private static var _tmpRect:Rectangle = new Rectangle();
		
		private function _add (bs:SpaceObject, x:Number, y:Number, width:Number, height:Number):Boolean {
			if (content.length < MIN_CONTENT_LENGTH && !isSplit) {
				content.push(bs);
				return true;
			}
			if (content.length == MIN_CONTENT_LENGTH && !isSplit) { 
				// distribute pile of objects on children as far as this is possible
				isSplit = true;
				for (var i:int = content.length - 1; i >= 0; i -= 1) {
					var e:SpaceObject = content[i];
					if (e.isContained(aRect)) {
						if (!a) a = new BTSpace(aRect.x, aRect.y, aRect.width, aRect.height).setOwner(owner) as BTSpace;
						a._internalAdd(content.splice(i, 1)[0]);
						continue;
					}
					if (e.isContained(bRect)) {
						if (!b) b = new BTSpace(bRect.x, bRect.y, bRect.width, bRect.height).setOwner(owner) as BTSpace;
						b._internalAdd(content.splice(i, 1)[0]);
					}
				}
			}
			_tmpRect.x = x;
			_tmpRect.y = y;
			_tmpRect.width = width;
			_tmpRect.height = height;
			if (aRect.containsRect(_tmpRect)) {
				if (!a) a = new BTSpace(aRect.x, aRect.y, aRect.width, aRect.height).setOwner(owner) as BTSpace;
				return a._add(bs,x,y,width,height);
			}
			if (bRect.containsRect(_tmpRect)) {
				if (!b) b = new BTSpace(bRect.x, bRect.y, bRect.width, bRect.height).setOwner(owner) as BTSpace;
				return b._add(bs,x,y,width,height);
			}
			content.push(bs);
			return true;
		}
		
		override protected function _internalRemove (bs:SpaceObject):Boolean {
			if (_rm(bs, bs.x, bs.y, bs.width, bs.height)) {
				bs.owner = null;
				_totalContentCount -= 1;
				return true;
			}
			return false;
		}
		
		private function _rm (bs:SpaceObject, x:Number, y:Number, width:Number, height:Number):Boolean {
			if (area.x > x + width || area.y > y + height || area.width + area.x < x || area.height + area.y < y)
				return false;
			var idx:int = content.indexOf(bs);
			if (idx >= 0) {
				content.splice(idx, 1);
				return true;
			}
			if (a && a._internalRemove(bs)) {
				if (a.isEmpty) a = null;
				return true;
			}
			if (b && b._internalRemove(bs)) {
				if (b.isEmpty) b = null;
				return true;
			}
			return false;
		}
		
		override public function enlistContent (area:Rectangle, appendTo:Vector.<SpaceObject>)
			:Vector.<SpaceObject> {
			//trace("Rect", this.area,content.length,aRect,bRect);	
			for each (var bs:SpaceObject in content) {
				if (bs.intersects(area)) appendTo.push(bs);
			}
			if (a && a.area.intersects(area)) a.enlistContent(area, appendTo);
			if (b && b.area.intersects(area)) b.enlistContent(area, appendTo);
			return appendTo;
		}
		
		override public function getObjectsAt(x:Number, y:Number, appendTo:Vector.<SpaceObject>)
			:Vector.<SpaceObject> {
			for each (var bs:SpaceObject in content) {
				if (bs.contains(x, y)) appendTo.push(bs);
			}
			if (a && a.area.contains(x, y)) a.getObjectsAt(x, y, appendTo);
			if (b && b.area.contains(x, y)) b.getObjectsAt(x, y, appendTo);
			return super.getObjectsAt(x, y, appendTo);
		}
		
		override public function objectMoved(obj:SpaceObject, oldx:Number, oldy:Number, newx:Number, newy:Number):Space 
		{
			_rm(obj, oldx, oldy, obj.width, obj.height);
			_add(obj, newx, newy, obj.width, obj.height);
			if (_owner) {
				_owner.markArea(oldx, oldy, obj.width, obj.height);
				_owner.markArea(newx, newy, obj.width, obj.height);
			}
			return this;
		}
	}

}